﻿using System;
using System.Collections.Generic;

//作业第二题的线性筛解法，时空复杂度均为O(n)，相比最开始的做法（O（n*sqrt(x）)）降低了时间复杂度
namespace myprogram
{
    class Program
    {
        public static List<int> Fun(int a)      //用线性筛筛出从1-a的所有素数
        {
            if (a < 2)   
                return new List<int>();     //无效输入，返回空列表，到时候不会显示出任何数

            bool[] isHS = new bool[a + 1];    //表示这个数是否是合数
            for (int i = 0; i <= a; i++)
                isHS[i] = false;     //初始化为全0

            List<int> primes = new List<int>();    //存放所有筛出的质数

            for (int i = 2; i <= a; i++)
            {
                if (isHS[i]==false) { primes.Add(i); }
                for (int j = 0; j < primes.Count; j++)
                {
                    if (i * primes[j] > a) break;   //超出范围
                    isHS[i * primes[j]] = true;
                    if ((i % primes[j]) == 0) break;    //保证每个质数都是由它的最小公因子筛出来的
                }

            }
            return primes;
        }

        public static void Main()
        {
            Console.WriteLine("请输入数据的上、下限：");
            string input = Console.ReadLine();
            string[] parts = input.Split(' ');
            int min = int.Parse(parts[0]);
            int max = int.Parse(parts[1]);
            var primes = Fun(max);
            if (primes.Count == 0)
            {
                Console.WriteLine($"{min}到{max}之间没有质数");
                return;
            }
            Console.WriteLine($"{min}到{max}之间的所有质数为：");
            int count = 0;   //计数，用于10个一行输出
            foreach (var prime in primes)
            {
                if (prime < min)
                    continue;
                Console.Write(prime + " ");
                count++;
                if (count % 10 == 0)
                    Console.WriteLine();  //输满10个就换行
            }
        }
    }

}